package q658_findClosestElements;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Solution_1 {
    /*
    特殊的解法：
    用两个优先队列 一个存大于x的 另一个存小于等于x的 然后小于等于x的队列要逆序排列
    这样每个队列的头部就是最接近x的 依次比较并弹出 加入到res中即可
     */
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> res = new ArrayList<>();
        PriorityQueue<Integer> pq1 = new PriorityQueue<>((a, b) -> b - a);
        PriorityQueue<Integer> pq2 = new PriorityQueue<>();
        for (int i : arr) {
            if (i <= x) pq1.offer(i);
            else pq2.offer(i);
        }
        for (int i = 0; i < k; i++) {
            if (pq1.isEmpty()) {
                res.add(pq2.poll());
                continue;
            }
            if (pq2.isEmpty()) {
                res.add(pq1.poll());
                continue;
            }

            int a = pq1.peek(), b = pq2.peek();
            if (Math.abs(a - x) <= Math.abs(b - x)) res.add(pq1.poll());
            else res.add(pq2.poll());
        }
        res.sort(Comparator.comparingInt(a -> a));
        return res;
    }
}
